from typing import List


def bubble_sort(arr: List[int]) -> List[int]:
    """实现冒泡排序算法"""
    arr = arr.copy()  # 避免修改原列表
    n = len(arr)

    # 遍历所有数组元素
    for i in range(n):
        swapped = False

        # 最后i个元素已经就位
        for j in range(0, n - i - 1):
            # 遍历数组从0到n-i-1
            # 交换元素如果当前元素大于下一个元素
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # 如果没有交换，说明数组已经有序，可以提前退出
        if not swapped:
            break

    return arr